package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
最长递增子序列的长度
输入 4 2 3 1 5
输出 3 （因为 2 3 5组成了最长递增子序列）
in
5
4 2 3 1 5

out
3
 */
public class j最长递增子序列LISbyDP {
	public static void main(String[] args) {
		j最长递增子序列LISbyDP test = new j最长递增子序列LISbyDP();
		test.useDP();
	}
	
	/**
	 * 前置方法
	 */
	public void useDP() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = scanner.nextInt();
		}
		int[] dp = new int[N];
		int res = DP(N, arr, dp);
		System.out.println(res);
	}
	
	/**
	 * O(N^2)
	 * @param N
	 * @param arr
	 * @param dp
	 * @return
	 */
	public int DP(int N, int[] arr, int[] dp) {
		dp[0] = 1;//默认声明dp首元素的值 = 1；代表默认的“最长递增子序列”的长度 = 1
		int res = -1;
		for (int index = 1; index < N; index++) {//从索引1开始
			int count = 1;//声明当前“最长递增子序列”的长度
			for (int before = index - 1; before >= 0; before--) {//往回遍历dp；寻找“能把当前元素arr[index]合法地放入的‘历史最长递增子序列’的最后一个元素”A的索引
				if (arr[before] < arr[index]) {//找到了A的索引
					count = Math.max(count, dp[before] + 1);//判断这个"加了arr[index]的历史最长递增子序列"的长度是否 > 当前“最长递增子序列”的长度
				}
			}
			dp[index] = count;//安全填入
		}//至此，填写dp的活计算是完成了
		for (int index = 0; index < N; index++) {//我们遍历一遍dp；来寻找最长的递增子序列
			res = Math.max(res, dp[index]);
		}
		return res;
	}
	
	
}
